Bloque 2: Fundamentos de la construcción de árboles de decisión

Analítica basada en árboles de clasificación y regresión

¿Qué es un árbol de decisión?

Un árbol de decisión es un mapa de posibles resultados en una serie de decisiones relacionadas. Un diagrama que muestra la probabilidad estadística o determina un curso de una acción. Muestra a los analistas y, a los que toman las decisiones, qué pasos deben tomar y cómo las diferentes elecciones podrían afectar todo el proceso. Todo ello soportado en datos.

Los árboles de decisión comienzan con un nodo, del cual salen otros en función de las opciones que se presenten, y de cada una de estas, otros. Existen tres tipos diferentes de nodos:

• Nodos de decisión: Se le representa con un cuadrado y muestra una decisión que se tomará.

• Nodos de probabilidad: Está representado por un círculo y muestra las probabilidades de ciertos resultados.

• Nodos terminales: Son de forma triangular, y muestra el resultado definitivo de una ruta de decisión.

Otros conceptos importantes:

*Otro concepto importante a tener en cuenta son las

• Ramificaciones. Estas se representan por líneas entre los nodos e indican un posible resultado o acción dentro del árbol.

• Hojas: Las hojas son las terminaciones de todas las ramas (el número de triángulos o nodos terminales)

¿Cómo hacemos un árbol de decisión?

Para realizar un árbol de decisión, podemos seguir los siguientes pasos:

1. Comenzamos con la decisión principal: Comenzaremos dibujando un cuadro que será el nodo principal. Luego, hacia la derecha comenzamos a hacer las ramificaciones, que representan las posibles decisiones y las etiquetamos.

2. Agregamos a cada ramificación nodos de decisión y probabilidad: esto hace que se expanda el árbol del siguiente modo:

• Si otra decisión es necesaria, entonces colocamos un cuadro que representa un nodo de decisión.

• Si el resultado es incierto, dibujamos un círculo (que representa los nodos de probabilidad), cuando tenemos un evento en el cual conocemos la probabilidad.

• Si el problema por medio de esa ramificación ya finaliza ponemos un triángulo

Desde cada nodo de decisión, dibuja soluciones posibles con ramificaciones. Desde cada nodo de probabilidad, dibuja líneas que representen los resultados posibles. Si deseas analizar tus opciones de forma numérica, incluye la probabilidad de cada resultado y el costo de cada acción.

3. Continúa con la expansión hasta que cada línea alcance un extremo, lo que significa que no hay más decisiones que tomar o resultados probables que considerar. Luego, asigna un valor a cada resultado posible. Puede ser una puntuación abstracta o un valor financiero. Agrega triángulos para indicar los extremos.

Con un árbol de decisión completo, ya estás listo para comenzar a analizar la decisión que enfrentas.

Ventajas y desventajas

Los árboles de decisión siguen siendo populares por razones como las siguientes:

• Son muy fáciles de entender

• Pueden ser útiles con o sin datos fehacientes, y cualquier dato requiere una preparación mínima

• Se pueden agregar nuevas opciones a los árboles existentes

• Su valor al seleccionar la mejor de numerosas opciones

• Se combinan fácilmente con otras herramientas de toma de decisiones

• Podemos encontrar un valor esperado y optimizarlo para encontrar la mejor decisión.

Sin embargo, los árboles de decisión pueden volverse excesivamente complejos. En esos casos, un diagrama de influencia más compacto puede ser una buena alternativa. Los diagramas de influencia se enfocan en los objetivos, las entradas y las decisiones fundamentales.

Ejemplo de árbol de creación decisión Petro Enterprises

Para entender la construcción de un árbol hagamos un ejemplo:

Petro Enterprises es una compañía de petróleos de Texas. La compañía Petro tiene una opción intransferible a corto plazo para perforar en una determinada parcela de tierra. La opción es el único acuerdo comercial en el que la empresa está involucrada ahora o que esperar considerar entre ahora y el 31 de diciembre de 1967, momento en el que se terminaría la perforación si se ejerciera la opción.

Dos recientes perforaciones en seco en otros lugares han reducido los activos líquidos netos de la compañía Petro a 130.000 dólares, y William Snyder, presidente y principal accionista, debe decidir si Petro debe ejercer su opción o dejarla expirar. La opción expirará dentro de dos semanas si no se inicia la perforación para entonces.

Snyder tiene tres opciones posibles:

1. Perforar inmediatamente

2. Pagar para que se realice una prueba sísmica en los próximos días, y luego, en función del resultado de la prueba, decidir si se perfora o no.

3. Dejar que la opción expire

Una vez descritas las posibles opciones de Snyder, también debemos conocer algo sobre sus posibles consecuencias económicas. Para conservar el capital y mantener la flexibilidad, Petro subcontrata todas las perforaciones y pruebas sísmicas; además, vende inmediatamente los derechos de cualquier petróleo descubierto, en lugar de desarrollar los campos petrolíferos por sí misma. Puede hacer que la prueba sísmica se lleve a cabo con poca antelación y con tarifas de horas extras por una tarifa fija de 30.000 dólares, y el pozo puede perforarse por una tarifa fija de 100.000 dólares. Una gran compañía petrolera ha prometido que si Petro perfora y descubre petróleo, comprará todos los derechos de Petro por un precio fijo de 400.000 dólares.

Para completar la descripción, es necesario conocer las probabilidades asignadas a las distintas contingencias. El geólogo de la empresa ha examinado la geología de la región y afirma que existe una probabilidad de 0,55 de que, si se hunde un pozo, se descubra petróleo. Los datos sobre la fiabilidad de la prueba sísmica indican que si el resultado de la prueba es favorable, la probabilidad de encontrar petróleo aumentará a 0,85; pero si el resultado de la prueba es desfavorable, bajará a 0,10. El geólogo ha calculado que hay una probabilidad de 0,60 de que el resultado sea favorable si se hace la prueba. Existe una sencilla, pero importante, interrelación lógica entre estas probabilidades, si quieres conocer más acerca de ello puedes verlo en la referencia: Schlaifer, Analysis of Decisions Under Uncertainty, op. cit, Chapter 9.

Este problema de decisión que implica incertidumbre puede estructurarse en forma del árbol de decisión que se muestra a continuación. El árbol muestra las probabilidades, basadas en el juicio del geólogo de la empresa, de los distintos eventos.

Podemos ver que con las consecuencias y las probabilidades podemos ir construyendo un árbol de decisión para esta compañía.

Ejercicio

Somos trabajadores de un banco encargados de la cobranza. Queremos tomar la determinación si llamar o no llamar a los clientes en los 5 y/o 10 días de adeudos.

Tenemos alguna información importante. Por medio de un modelo de riesgos, hemos determinado la probabilidad de pago de los clientes determinada y la llamaremos \(p\). A casa cliente se le prestó una cantidad de dinero \(B\).

Nosotros podemos tomar la decisión si utilizamos a nuestros client partners para que se comuniquen con las personas o no, pero debemos de considerar que la llamada nos cuesta $8. Además, si el cliente no paga (sea que se le llame o que no se le llame), lo mandamos a una agencia externa y solo recibimos el 80% del total del préstamo.

Discute con tus compañeros el problema y realiza un árbol de decisiones para poder tomar la mejor decisión.

---

Los árboles de decisión en minería de datos y machine learning

Recordemos que, quizás la idea general que muchas personas tienen sobre machine learning…

Lo que es en realidad…

Como ya hemos visto con la ayuda de tidymodels y h2o, un árbol de decisión también puede usarse para ayudar a crear modelos predictivos automáticos, que pueden entrenarse mediante aprendizaje automático, en minería de datos y estadística. Conocido como lenguaje basado en árboles de decisión, estos métodos toman en consideración las observaciones sobre un elemento para predecir un valor.

En estos árboles de decisión, los nodos representan datos en lugar de decisiones. Este tipo de árbol también se conoce como árbol de clasificación. Cada ramificación contiene un conjunto de atributos o reglas de clasificación asociadas a una etiqueta de clase específica, que se halla al final de la ramificación.

Estas reglas, también conocidas como reglas de decisión, se pueden expresar en una cláusula “Si… entonces…”. Cada valor de datos o decisión forma una cláusula, de tal forma que, por ejemplo, “si las condiciones 1, 2 y 3 se cumplen, entonces el resultado X será el resultado definitivo con certeza Y”.

Cada dato adicional ayuda a que el modelo prediga de forma más precisa a qué conjunto finito de valores pertenece el asunto en cuestión. Esa información se puede usar posteriormente como una entrada en un modelo más grande de toma de decisiones.

A veces la variable predicha será un número real, como un precio. Los árboles de decisión con resultados posibles, infinitos y continuos se llaman árboles de regresión.

Un árbol de decisión se considera ideal cuando representa la mayor cantidad de datos con el menor número de niveles o preguntas. Los algoritmos diseñados para crear árboles de decisión optimizados incluyen CART (el más utilizado y el que estudiaremos en esta materia), ASSISTANT, CLS y ID3/4/5. Un árbol de decisión también se puede generar mediante la creación de reglas de asociación, ubicando la variable objetivo a la derecha.

Cada método debe determinar cuál es la mejor forma de dividir los datos en cada nivel. Los métodos comunes para hacerlo incluyen la medición de la impureza de Gini, la obtención de información y la reducción de variaciones.

Ventajas y desventajas

Emplear los árboles de decisión en el aprendizaje automático tiene numerosas ventajas:

• El costo del uso del árbol para predecir los datos disminuye con cada punto de datos adicional.

• Funciona para los datos numéricos o categóricos.

• Puede modelar problemas con múltiples resultados.

• Usa un modelo de caja blanca (lo que hace que los resultados sean fáciles de explicar). Los algoritmos caja blanca son aquellos que normalmente trabajan sobre funciones matemáticas o de lógica que el programador conoce muy bien y que va modificando para mejorar el rendimiento del algoritmo.

• La fiabilidad de un árbol se puede cuantificar y poner a prueba.

• Tiende a ser preciso independientemente de si viola las suposiciones de los datos de origen.

Pero también tienen algunas desventajas:

• Cuando se presentan datos categóricos con múltiples niveles, la información obtenida se inclina a favor de los atributos con mayoría de niveles.

• Los cálculos pueden volverse complejos al lidiar con la falta de certezas y numerosos resultados relacionados.

• Las conjunciones entre nodos se limitan a AND, mientras que los gráficos de decisión admiten nódulos relacionados mediante OR.

Para tener en cuenta sobre árboles

• Son un tipo de algoritmos de aprendizaje supervisado (es decir, existe una variable objetivo predefinida).

• Principalmente usados en problemas de clasificación.

• Las variables de entrada y salida pueden ser categóricas o continuas.

• Divide el espacio de predictores (variables independientes) en regiones distintas y no sobrepuestas. Por ejemplo:

• Se divide la población o muestra en conjuntos homogéneos basados en la variable de entrada más significativa.

• La construcción del árbol sigue un enfoque de división binaria recursiva (top-down greddy approach). Greedy -> analiza la mejor variable para ramificación sólo en el proceso de división actual.

Ejemplo

Tenemos un conjunto de datos correspondiente a 30 estudiantes y 3 variables:

*Género (hombre/mujer),

*Clase (IX/X) y

*Altura (5 a 6 pies).

Sabemos que 15 estudiantes juegan cricket en su tiempo libre. Queremos crear un modelo para predecir quien jugará cricket. Segregar estudiantes basados en todos los valores de las 3 variables e identificar aquella variable que crea los conjuntos más homogéneos de estudiantes y que a su vez son heterogéneos entre ellos.

¿Qué variable es la más significativa para la mejor división de la población?

Terminología a la hora de modelar

*Nodo raíz: población completa o muestra

• Ramificación

• Nodo de decisión

• Nodo terminal y hoja

*Poda

*Rama/sub-árbol

*Nodos padre e hijo

Árboles de regresión versus árboles de clasificación

El modelo de conjunto de árboles consta de un conjunto de árboles de clasificación y regresión (CART), el cual fue desarrollado por Breiman et al en 1984.

Ahora bien, ¿cuál es la diferencia entre árboles de clasificación y regresión?*

Regresión	Clasificación
Variable a predecir es continua	Variable a predecir es categórica
Valores de los nodos terminales se reducen a la medida de las observaciones en esa región	El valor en el nodo terminal se reduce a la moda de las observaciones del conjunto de entrenamiento que han llegado o caído en la región.

En los árboles de decisión comenzamos por una pregunta. Aquí hay un ejemplo simple de un CART que clasifica si a alguien le gustará un hipotético juego de computadora X, dónde la pregunta es ¿Le gustan los juegos de computadora X?

Clasificamos a los integrantes de nuestro conjunto de datos en diferentes ramas según la edad y se la asigna una puntuación correspondiente en el vértice.

Un CART es un poco diferente de los árboles de decisión, en los que la hoja solo contiene valores de decisión. En CART, se asocia una puntuación real a cada una de las hojas, lo que nos da interpretaciones más ricas que van más allá de la clasificación. Esto también permite un enfoque unificado y basado en principios para la optimización.

Por lo general, un solo árbol no es lo suficientemente fuerte para usarse en la práctica. Lo que se utiliza realmente es el modelo de conjunto, que suma la predicción de varios árboles juntos.

A continuación,se muestra un ejemplo de un conjunto de dos árboles. Las puntuaciones de predicción de cada árbol individual se suman para obtener la puntuación final. Si miras el ejemplo, un dato importante es que los dos árboles intentan complementarse.

Matemáticamente, podemos escribir nuestro modelo en la forma \[ \hat{y}= \sum_{k=1}^K f_k(x_i), \space f_k \in \digamma \] donde:

• \(x_i\) es el individuo \(i\),

• \(K\) es el número de árboles,

• \(f\) es una función del espacio funcional \(\digamma\), y

• \(\digamma\) es el conjunto de todos los CART posibles.

Se busca optimizar una función objetivo dada por:

\[ obj(\theta) = \sum_{i=1}^n l(y_i,\hat y_i)+\sum_{k=1}^K \varOmega (f_k) \]

donde la primera parte representa la pérdida del entrenamiento y la segunda la regularización.

Aumento de árboles

Ya teniendo representado el modelo, pasamos al entrenamiento: ¿Cómo debe aprender los árboles? La respuesta es, como todos los modelos de aprendizaje supervisado: ¡defina una función objetivo y optimícela!

Sea la siguiente función objetivo (recuerde que siempre debe contener la pérdida de entrenamiento y la regularización):

\[ obj = \sum_{i=1}^n l(y_i,\hat y_i^{(t)})+\sum_{i=1}^t \varOmega (f_i) \]

Entrenamiento aditivo

La primera pregunta que queremos hacernos: ¿cuáles son los parámetros de los árboles? Puede encontrar que lo que necesitamos que aprenda son esas funciones \(f_i\), cada uno con la estructura del árbol y puntuaciones en las hojas. Aprender la estructura del árbol es mucho más difícil que el problema de optimización tradicional en el que simplemente puede tomar el gradiente. Es difícil que se aprenda todos los árboles al mismo tiempo.

Por eso, se usa una estrategia aditiva: organizando lo que ha aprendido y agrega un árbol nuevo a la vez. Se va escribiendo el valor de predicción en el paso \(t\) como \(\hat y_i^{(t)}\) . Entonces se puede obtener:

\[ \begin{array}{l} \hat y_i^{(0)}=0 \\ \hat y_i^{(1)}=f_1(x_i)=\hat y_i^{0}+f_1(x_i) \\ \hat y_i^{(2)}=f_1(x_i)+f_2(x_i)=\hat y_i^{1}+f2i(x_i) \end{array} \]

Entonces ahora nos falta ¿qué árbol queremos en cada paso? lo natural es sumar el que optimice la función objetivo

\[ \begin{align} obj^{(t)} & = \sum_{i=1}^n l(y_i,\hat y_i^{(t)})+\sum_{i=1}^t \varOmega (f_i) \\ & = \sum_{i=1}^n l(y_i,\hat y_i^{(t-1)}+f_t(x_i))+ \varOmega (f_t) + \text{constant} \end{align} \] Si consideramos el uso del error cuadrático medio (MSE) como la función de pérdida, el objetivo se convierte en

\[ \begin{align} obj^{(t)} & = \sum_{i=1}^n (y_i-(\hat y_i^{(t-1)}+f_t(x_i)))^2+\sum_{i=1}^t \varOmega (f_i) \\ & = \sum_{i=1}^n [2(\hat y_i^{(t-1)} - y_i)f_t(x_i)+f_t(x_i)^2]+ \varOmega (f_t) + \text{constant} \end{align} \] La forma de MSE es amigable, con un término de primer orden (generalmente llamado residual) y un término cuadrático. Para otras pérdidas de interés (por ejemplo, pérdida logística), no es tan fácil conseguir una forma tan bonita. Entonces, en el caso general, tomamos la expansión de Taylor de la función de pérdida hasta el segundo orden:

\[ obj^{(t)} = \sum_{i=1}^n [l(y_i,\hat y_i^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)] + \varOmega (f_t) + \text{constant} \]

donde, \[ \begin{align} g_i = \partial_{\hat{y}_i^{(t-1)}}l(y_i,\hat{y}_i^{t-1})\\ h_i = \partial^2_{\hat{y}_i^{(t-1)}}l(y_i,\hat{y}_i^{t-1}) \end{align} \] Después de eliminar todas las constantes, el objetivo específico en el paso se convierte en

\[ \sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\varOmega (f_t) \]

Este se convierte en la función objetivo de optimización para el nuevo árbol. Una ventaja importante de esta definición es que el valor de la función objetivo solo depende de y \(g_i\) y \(h_i\). Así es como algoritmo como XGBoost admite funciones de pérdida personalizadas. Se puede optimizar cada función de pérdida, incluida la regresión logística y la clasificación por pares, utilizando exactamente el mismo solucionador que toma \(g_i\) y \(h_i\) como entrada!

La puntuación de estructura

Aquí está la parte mágica de la derivación. Después de reformular el modelo de árbol, podemos escribir el valor objetivo con el \(t\)-th árbol como:

\[ \begin{align} obj^{(t)} & \approx \sum_{i=1}{n}[g_iw_{q(x_i)}+\frac{1}{2}h_iw^2_{q(x_i)}]+\gamma T+\frac{1}{2}\lambda \sum_{j=1}^Tw^2_j \\ & = \sum_{j=1}^T [(\sum_{i\in I_j}g_i)w_j+\frac{1}{2}(\sum_{i\in I_j}h_i+\lambda)w_j^2]+\gamma T \end{align} \]

donde, \(I_j= \{ i |q(x_i)=j\}\) es el conjunto de índices de puntos de datos asignados a la \(j\)-th hoja. Observe que en la segunda línea hemos se cambia el índice de la suma porque todos los puntos de datos en la misma hoja obtienen la misma puntuación. Podríamos comprimir aún más la expresión definiendo \(G_j = \sum_{i\in I_j}g_i\) y \(H_j = \sum_{i\in I_j}h_i\)

\[ obj^{(t)} = \sum_{j=1}^T [G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2]+\gamma T \]

En esta ecuación, \(w_j\) son independientes entre sí, la forma \(G_jw_j+ \frac{1}{2}(H_j+\lambda)w_j^2\) es cuadrática, y por tanto podemos encontrar el mejor \(w_j\) para la estructura dada \(q(x)\) y podemos redur la función objetivo de la siguiente forma:

\[ \begin{align} w_j^* &= -\frac{G_j}{H_j+\lambda} \\ obj^* &= - \frac{1}{2}\sum_{j=1}^T \frac{G_j^2}{H_j+\lambda}+\gamma T \end{align} \] La última ecuación mide qué tan buena estructura de árbol es \(q(x)\):

Todo esto suena un poco complicado, veamos cómo se pueden calcular las puntuaciones por medio de la imagen. Básicamente, para una estructura de árbol determinada, empujamos las estadísticas \(g_i\) y \(h_i\) a las hojas a las que pertenecen, sume las estadísticas y use la fórmula para calcular qué tan bueno es el árbol. Esta puntuación es como la medida de impurezas en un árbol de decisión, excepto que también toma en cuenta la complejidad del modelo.

Estructura del árbol

Luego de medir qué tan bueno es el árbol, lo ideal sería enumerar todos los árboles posibles y elegir el mejor. En la práctica sabemos que no debemos hacerlo por el coste computacional que implica.

Específicamente, tratemos de dividir una hoja en dos hojas, y la puntuación que se obtiene es

\[ Gain = \frac{1}{2} \left[ \frac{G^2_L}{H_L+\lambda}+\frac{G^2_R}{H_R+\lambda}- \frac{(G_L+G_R)^2}{H_L+H_R+\lambda} \right]-\gamma \]

Esta fórmula se puede descomponer como:

1. la puntuación en la nueva hoja izquierda,

2. la puntuación en la nueva hoja derecha,

3. La puntuación en la hoja original, y

4. regularización en la hoja adicional.

Podemos ver un hecho importante aquí: si la ganancia es menor que \(\gamma\), sería mejor no agregar esa rama.

¡Estas son exactamente las técnicas de poda en modelos basados en árboles! Al utilizar los principios del aprendizaje supervisado, naturalmente podemos encontrar la razón por la que estas técnicas funcionan.

Para datos de valor real, generalmente queremos buscar una división óptima. Para hacerlo de manera eficiente, colocamos todas las instancias de forma ordenada, como en la siguiente imagen.

Un escaneo de izquierda a derecha es suficiente para calcular la puntuación de estructura de todas las posibles soluciones de división, y podemos encontrar la mejor división de manera eficiente.

Ventajas y desventajas respecto a otros algoritmos o modelos

Ventajas

• Fácil de entender

• Útil en exploración de datos: identificar importancia de variables a partir de cientos de variables.

• Menos limpieza de datos: outliers y valores faltantes no influencian el modelo (A un cierto grado)

• El tipo de datos no es una restricción

• Es un método no paramétrico (i.e., no hay suposición acerca del espacio de distribución y la estructura del clasificador)

Desventajas

• Sobreajuste

• Pérdida de información al categorizar variables continuas

• Precisión: métodos como SVM y clasificadores tipo ensamblador a menudo tienen tasas de error 30% más bajas que CART (Classification and Regression Trees)

• Inestabilidad: un pequeño cambio en los datos puede modificar ampliamente la estructura del árbol. Por lo tanto la interpretación no es tan directa como parece.

¿Cómo decide un árbol dónde ramificarse?

La decisión de hacer divisiones estratégicas afecta altamente la precisión del árbol. Los criterios de decisión son diferentes para árboles de clasificación y regresión. Existen varios algoritmos para decidir la ramificación. La creación de subnodos incrementa la homogeneidad de los subnodos resultantes. Es decir, la pureza del nodo se incrementa respecto a la variable objetivo. Al final, se prueba la división con todas las variables y se escoge la que produce subnodos más homogéneos.

Algunos algoritmos más comunes para la selección:

• Índice Gini,

• Chi Cuadrado,

• Ganancia de la información, y

• Reducción en la varianza

Índice Gini

Este índice se basa en la expresión: “Si seleccionamos aleatoriamente dos ítems de una población, entonces estos deben ser de la misma clase y la probabilidad de esto es 1 si la población es pura”.

Algunas consideraciones:

1. Variable objetivo categórica: “Success” o “Failure”

2. Solo divisiones binarias

3. A mayor valor de índice Gini, mayor la homogeneidad

4. CART (Classification and Regression Tree) usa el método de Gini para la división binaria.

Para su cálculo::

1. Calcular Gini para los subnodos usando la fórmula de la suma de los cuadrados de probabilidad para success y failure \((p^2 + q^2)\).

2. Calcular Gini para la división usando score Gini ponderado para cada nodo de la división.

Para entender mejor todo esto, veamos un ejemplo:

Género	Clase
Mujer \(0.2^2+0.8^2=0.68\)	IX \(0.43^2+0.57^2=0.51\)
Hombre \(0.65^2+0.35^2=0.55\)	X \(0.56^2+0.44^2=0.51\)
Pond. \((10/30)0.68+(20/30)0.55 = 0.59\)	Pond. \((14/30)0.51 + (16/30)0.51 = 0.51\)

• ¿Cuál es el resultado para la variable “Altura”?

• ¿Cuál es el variable que se debe escoger para la primera división?

Chi cuadrado

Un algoritmo para encontrar la significancia estadística de las diferencias entre subnodos y un nodo padre. Se mide a partir de la suma de los cuadrados de las diferencias estandarizadas entre las frecuencias observadas y esperadas de la variable objetivo.

Algunas consideraciones:

1. Variable objetivo categórica “Success” o “Failure”.

2. Dos o más divisiones

3. A más alto valor de Chi-Cuadrado, más alta la significancia estadística de las diferencias entre cada nodo y el nodo padre.

4. Fórmula: \(\left[\frac{(Real-Esperado)^2}{Esperado} \right]^{\frac{1}{2}}\)

Para su cálculo:

1. Calcular Chi-Cuadrado para cada nodo individualmente a través de la desviación para ambos: Success y Failure

2. Calcular Chi-Cuadrado de la división usando la suma de todos los Chi-Cuadrado de Success y Failure de cada nodo en la división.

Continuando con el ejemplo anterior, pero teniendo las siguientes consideraciones:

1. Para el nodo “Mujer”. Los valores reales para “Play Cricket” y “Not Play Cricket” son 2 y 8, respectivamente.

2. Para calcular el valor esperado, asignaremos la misma probabilidad que su nodo padre (50%). Por lo tanto para ambos casos el valor sería 5 considerando el total de elementos “Mujer” (10).

3. Calcular las diferencias para usar en la fórmula, Real-Esperado. Para “Play Cricket” (2-5=-3) y para “No Play Cricket” (8-5=3)

4. Calcular Chi-Cuadrado del nodo para “Play Cricket” y “No Play Cricket” usando la fórmula completa \(\left[\frac{(Real-Esperado)^2}{Esperado} \right]^{\frac{1}{2}}\).

5. Seguir los pasos 1-4 para el caso del nodo “Hombre”.

6. finalmente sumar todos los Chi-Cuadrado para calcular el Chi-Cuadrado para la división de la variable Género.

Nodo	Play Cricket	Not Play	Total	Expected play	Expected not play	Deviation not play	Chi Square play	Chi Square not play
Female	2	8	10	5	5	- 3	1.34	1.34
Male	13	7	20	10	10	3	0.95	0.95

Por lo tanto el total Chi cuadrado es 4.58.

Podemos hacer el mismo procedimiento para la variable “Class”:

Nodo	Play Cricket	Not Play	Total	Expected play	Expected not play	Deviation not play	Chi Square play	Chi Square not play
IX	6	8	14	7	-1	1	0.38	0.38
X	9	7	16	8	1	-1	0.35	0.35

Por lo tanto el total Chi cuadrado es 1.46.

• ¿Cuál es el resultado para la variable “Altura”?

• ¿Cuál es el variable que se debe escoger para la primera división?

Ganancia de información

Un nodo menos impuro requiere menos información para ser descrito mientras un nodo más impuro necesita más información. La teoría de la información es una medida para definir este grado de desorganización en un sistema denominado como Entropía. Decimos que una muestra completamente homogénea = entropía 0, y decimos que es igualmente dividida (50% – 50%) = entropía 1.

La entropía la podemos calcular de la siguiente forma:

\[ \text{entropia} = -p \log_2(p) - q\log_2(q) \]

donde \(p\) es la probabilidad de success y \(q\) la probabilidad de failure. La entropía es también usada con variable objetivo categórica. Se escoge la división con la entropía más baja comparada con el nodo padre y otras variables de división.

Para calcular entropía del nodo padre, calculamos la entropía de cada uno de los nodos de forma individual y calcular la media ponderada de todos los nodos disponibles en la división.

Continuando con el ejemplo,

Criterio	Entropía
Nodo padre	-(15/30) log2(15/30)-(15/30) log2(15/30)= 1
Nodo mujer	-(2/10)log2(2/10)-(8/10)log2(8/10)=0.72
Nodo hombre	-(13/20) log2 (13/20) – (7/20) log2 (7/20) = 0.93
Género ponderado	(10/30)0.72 + (20/30)0.93 = 0.86
Nodo Clase IX	-(6/14) log2 (6/14) – (8/14) log2 (8/14) = 0.99
Nodo Clase X	-(9/16) log2 (9/16) – (7/16) log2 (7/16) = 0.99
Clase ponderado	(14/30)0.99 + (16/30)0.99 = 0.99

La entropía para la división por la variable “Género” es la más baja. Se puede derivar la ganancia de información a partir de la entropía así: 1-Entropía.

Reducción en la varianza (regresión)

Los algoritmos anteriores se aplicaban para problemas de clasificación con variables objetivo categórica. Por otra parte, la reducción en la varianza es un algoritmo usado para variables objetivo continuas (problemas de regresión). Este algoritmo usa la fórmula estándar de la varianza para escoger el criterio de división. La división con la varianza más baja se escoge para dividir la población:

\[ \text{Varianza}= \frac{\sum(X-\bar{X})^2}{n} \]

Para su cálculo primero calculamos la varianza en cada nodo, para luego calcular la varianza de cada división por un promedio ponderado de las varianzas de los nodos.

Continuando con el ejemplo, asumiremos que vamos a convertir los valores numéricos de 1 para play cricket y cero para no play cricket.

Criterio	Mean	Varianza
Nodo Padre	(15x1 + 15x0)/30 = 0.5	(15x(1-0.5)^2 + 15x(0-0.5)^2) / 30 = 0.25
Nodo Mujer	(2x1 + 8x0)/10=0.2	(2x(1-0.2)^2 + 8x(0-0.2)^2) / 10 = 0.16
Nodo Hombre	(13x1 + 7x0)/20=0.65	(13x(1-0.65)^2 + 7*(0-0.65)^2) / 20 = 0.23
Género ponderado		(10/30)x0.16 + (20/30) *0.23 = 0.21
Nodo Clase IX	(6x1 + 8x0)/14=0.43	(6x(1-0.43)^2 + 8x(0-0.43)^2) / 14= 0.24
Nodo Clase X	(9x1 + 7x0)/16=0.56	(9x(1-0.56)^2 + 7x(0-0.56)^2) / 16 = 0.25
Clase ponderado		(14/30)x0.24 + (16/30) x0.25 = 0.25

Parámetros del modelo y como evitar sobreajuste en árboles de decisión

El sobreajuste es uno de los desafíos más importantes en el proceso de modelación de árboles de decisión. Si no se definen límites, el árbol tendrá un 100% de precisión en el conjunto de datos de entrenamiento. En el peor caso tendrá una hoja por cada observación.

Dos formas de evitar el sobreajuste: (a) Definir restricciones sobre el tamaño del árbol y (b) Podar el árbol.

Definir restricciones sobre el tamaño del árbol (prepruning)

Uso de parámetros para definir un árbol. Los parámetros son independientes de la herramienta de programación (R & Python)

1. Mínimo de observaciones para dividir un nodo

• Mínimo número de muestras u observaciones que se requieren en un nodo para ser considerado para ramificación.

• Valores más altos previenen que el modelo aprenda relaciones muy específicas.

• Valores demasiado altos pueden causar un pobre ajuste del modelo. El parámetro debe ajustarse usando validación cruzada.

2. Mínimo número de observaciones para un nodo terminal

• Valores más bajos son necesarios para problemas de clases no balanceadas.

3. Máxima profundidad del árbol (vertical)

• Una mayor profundidad permite aprender relaciones más específicas.

• Debe ajustarse con validación cruzada.

4. Máximo número de nodos hoja

• Se puede definir en lugar de máxima profundidad. Profundidad n = máximo 2^n hojas

5. Máximo número de atributos a considerar para la ramificación

• Seleccionados aleatoriamente.

• Como regla general, la raíz cuadrada del número total de atributos funciona apropiadamente. Sin embargo, se debe probar hasta un 30%-40% del número total de atributos.

Poda del árbol (postpruning)

Su implementación es sencilla.

• Construir el árbol a un profundidad extensa.

• Remover las hojas que den un valor negativo comparado desde la raíz. Existen varios criterios que pueden ser utilizados, algunos basados en heurísticas y otros en parámetros de regularización (penalización).

Ejemplo: Supongamos que un nodo de decisión da una ganancia de -10 (pérdida de 10) y la siguiente ramificación da una ganancia de 20. Un árbol de decisión simple pararía en el paso uno, sin embargo, el proceso de poda considerará la ganancia general de +10 y mantendrá ambas hojas.

Librerías: El clasificador de árbol de decisión en la libraría de python Scikit actualmente no soporta el proceso de poda. Paquetes avanzados como xgboost lo incoporan. Por otra parte, el paquete de R rpart provee una función de poda directamente.

Referencias

• https://bookdown.org/rdpeng/RProgDA/functions.html)

• Tutorial - principal fuente de este bookdown https://www.analyticsvidhya.com/blog/2016/04/complete-tutorial-tree-based-modeling-scratch-in-python/

• Ejemplo de árboles de decisión https://www.guru99.com/r-decision-trees.html

• rpart.plot https://cran.r-project.org/web/packages/rpart.plot/rpart.plot.pdf

• Opciones de ploteo Rpart Tree http://www.milbo.org/rpart-plot/prp.pdf